This invention relates generally to programming tools, and more particularly to tools for instrumenting and optimizing heterogeneous programs written for different computer architectures.
A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever. The following notice applies to the software and data as described below and in the drawings hereto: Copyright (copyright) 1998, Microsoft Corporation, All Rights Reserved.
In a new programming paradigm, a program is now a collection of components. Each component publishes an interface without exposing its inner details. Thus, a component can internally exist in any form: Intel x86 binary, Intel IA-64 binary, Visual Basic (VB) byte codes, Java class files, or any Virtual Machine (VM) binary. A heterogeneous program consists of components in different forms. Heterogeneous programs already exist in some environments: in the Microsoft Windows 32-bit environment, a Visual Basic program is compiled into VB byte codes that can call native-compiled functions in a separate dynamic linked library. Similarly Java class files can call native functions. Intel""s IA-64 architecture allows IA-64 code to co-exist with x86 code.
To understand the behavior of a heterogeneous program, all its components, regardless of their form, have to be instrumented and analyzed in the same framework, otherwise, only partial information will be collected. It is important to note that systems that have been ported to several architectures are not sufficient to handle heterogeneous programs. For example, a system for VB byte codes that has been ported to x86, cannot provide a complete execution time analysis of a heterogeneous program consisting of VB byte codes and native x86 because each system operates in isolation on its own input.
Further, a heterogeneous program may consist of heterogeneous components. A heterogeneous component is a single component consisting of routines in different instruction sets. As the interface is well defined, components internally can use any instruction set. Each instruction set has its own advantages such as execution time, portability, and size.
All previous systems have been designed for homogeneous programs: conventional programs consisting of components in the same form. Some systems have been targeted to different architectures, but cannot work with heterogeneous programs. None of these systems can generate a heterogeneous component.
A large number of systems have been developed to help analyze and optimize homogeneous programs. The creation of xe2x80x9cPixiexe2x80x9d by MIPS Computers Systems, Inc. in 1986 started a class of basic block counting tools by inserting pre-determined sequence of instructions to record execution frequencies of basic blocks. xe2x80x9cEpoxiexe2x80x9d extended the technique by using relocations to eliminate dynamic translation overheads. David W. Wall. Systems for late code modification, in Code Generationxe2x80x94Concept, Tools Techniques, pp. 275-293, (Robert Giegrich and Susan L. Graham, eds, 1992). xe2x80x9cQPTxe2x80x9d further extended the technique by constructing spanning trees to reduce the number of basic blocks that are instrumented. James Larus and Thomas Ball, Rewriting executable files to measure program behavior, Software, Practice and Experience, vol. 24, no. 2, pp 197-218 (1994). xe2x80x9cPurifyxe2x80x9d instruments memory references to detect out-of-bounds memory accesses and memory leaks. Reed Hastings and Bob Joyce, Purify: Fast Detection of Memory Leaks and Access Errors, Proceedings of Winter Usenix Conference, January 1992.
xe2x80x9cOMxe2x80x9d allowed general transformations to be applied to a binary by converting the binary to an intermediate representation that can be easily manipulated. Amitabh Srivastava and David Wall, A Practical System for Intermodule Code Optimization at Link Time, Journal of Programming Language, 1(1):1-18 (1993). OM has been implemented on MIPS, DEC Alpha and Intel x86 architectures. xe2x80x9cEELxe2x80x9d uses a similar technique and provides an editing library for Sun SPARC architectures. James R. Larus and Eric Schnarr, EEL: Machine-Independent Executable Editing, Proceedings of SIGPLAN ""95 Conference on Programming Language Design and Implementation (1995). xe2x80x9cAltoxe2x80x9d and xe2x80x9cSpikexe2x80x9d are optimizers for the DEC Alpha architectures. K. De Bosschere and S. Debray, Alto: a Link-Time Optimizer for the DEC Alpha. Technical Report TR-96-16, Computer Science Department, University of Arizona (1996). David W. Goodwin, Interprocedural Dataflow Analysis in an Executable Optimizer, Proceedings of SIGPLAN ""97 Conference on Programming Language Design and Implementation (1997).
xe2x80x9cATOMxe2x80x9d extended OM by providing a flexible instrumentation interface for the DEC Alpha and Intel x86 systems. Amitabh Srivastava and Alan Eustace, ATOM: A System for Building Customized Program Analysis Tools, Proceedings of SIGPLAN ""94 Conference on Programming Language Design and Implementation (1994). However, ATOM does not allow modifications to a binary. xe2x80x9cEtchxe2x80x9d provided a similar system for x86 and xe2x80x9cBITxe2x80x9d for Java byte codes. T. Romer, G. Voelker, D. Lee, A. Wolman, W. Wong, H. Levy, B. Chen, and B. Bershad, Instrumentation and Optimization of Win32/Intel Executables Using Etch, Proceedings of the USENIX Windows NT Workshop (1997). Han Lee and Benjamin Zorn, BIT: A Tool for instrumenting Java bytecodes. Proceedings of the 1997 USENIX Symposium on Internet Technologies and Systems (1997).
None of these systems work on heterogeneous programs. Some of them have been ported to multiple architecture but they provide only a partial view when applied to heterogeneous programs as each implementation operates on its input in isolation. Although OM builds a symbolic representation, the representation was primarily designed for applying arbitrary transformations and is not sufficient to handle heterogeneous programs. None of these systems can generate heterogeneous components. ATOM provides a flexible interface for instrumentation only.
To understand the behavior of a heterogeneous program, all its components, regardless of their form, have to be instrumented and analyzed in the same framework, otherwise, only partial information will be collected. It is important to note that systems that have been ported to several architectures are not sufficient to handle heterogeneous programs. For example, a system for VB byte codes that has been ported to x86, cannot provide a complete execution time analysis of a heterogeneous program consisting of VB byte codes and native x86 because each system operates in isolation on its own input. Similarly, optimizing a heterogeneous program can require rearranging instructions across platform boundaries but such whole program optimization is known to provide performance advantages when the program is executed.
Therefore, there is a need to represent a heterogeneous program and its heterogeneous components in a fashion that permits the behavior of the program to be evaluated across architectural boundaries and optimization to be performed on the entire program.
The above-mentioned shortcomings, disadvantages and problems are addressed by the present invention, which will be understood by reading and studying the following specification.
Pre-defined performance tools enable instrumentation and optimization of a heterogeneous program by modifying a platform-neutral intermediate representation (IR) of the program. The intermediate representation is hierarchy of base elements that correspond to instructions, code blocks, procedures and components within the program. Each base element exports an application program interface (API) that provides for navigation, querying and modification of the corresponding element in the hierarchy. An API for the entire IR includes the APIs for the individual elements along with additional functionality. A user can request instrumentation and optimization of any level of the IR hierarchy and the performance tools perform the required modifications to the intermediate representation. When a modification requires inserting instructions, the performance tools add prologue and epilog code to connect the inserted instructions with the original IR instructions. The API for the IR also provides a commit primitive that delays actual changes to the IR until the commit primitive is invoked. The IR hierarchy can be extended by creating new elements and associated APIs from the base elements in the hierarchy.
When the IR instructions are translated into platform-specific instructions and executed, the modifications made to the intermediate representation provide the instrumentation and/or optimization of the heterogeneous program. Because the architecture specific details are removed in the intermediate representation, instrumentations and optimizations can be perform across what were previously incompatible boundaries between components in a heterogeneous program. Moreover, the performance tools can be applied at any level in the hierarchy to provide scalability in the instrumentation and optimization of the program.
The present invention describes systems, clients, servers, methods, and computer-readable media of varying scope. In addition to the aspects and advantages of the present invention described in this summary, further aspects and advantages of the invention will become apparent by reference to the drawings and by reading the detailed description that follows.